package algorithms.graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class DepthFirstOrder {

	private boolean[] marked;
	private Queue<Integer> pre;	//前序遍历
	private Queue<Integer> post;	//后序
	private Stack<Integer> reversePost;	//逆后序。就是拓扑排序的结果
	
	public DepthFirstOrder(Digraph g) {
		marked = new boolean[g.V()];
		pre  = new LinkedList<Integer>();
		post = new LinkedList<Integer>();
		reversePost = new Stack<Integer>();
		for(int v = 0; v < g.V(); v++){
			if(!marked[v])	dfs(g,v);
		}
	}

	private void dfs(Digraph g, int v) {
		pre.add(v);
		
		marked[v] = true;
		for(int w : g.adj(v)){
			if(!marked[w])
				dfs(g, w);
		}
		post.add(v);
		reversePost.push(v);
	}
	
	public Iterable<Integer> reversePost(){
		return reversePost;
	}
}
